package demo.practice.bfs;

import java.util.*;


public class P133 {
    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }


    public Node cloneGraph(Node node) {
        Map<Integer, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        map.put(node.val, new Node(node.val));
        Set<Integer>set = new HashSet<>();


        while (!queue.isEmpty()) {
            Node top = queue.poll();
            Node p = map.get(top.val);

            if(set.contains(top.val)) //访问过了
                continue;

            set.add(top.val);


            for (Node neighbor : top.neighbors) {
                if (map.containsKey(neighbor.val)) {
                    Node ch = map.get(neighbor.val);
                    p.neighbors.add(ch);
                } else {
                    Node ch = new Node(neighbor.val);
                    map.put(neighbor.val, ch);

                }
                queue.add(neighbor);
            }
        }
        return map.get(node.val);
    }

}
